package top.lcm668.study.oj.base.sortmethods.mergesort;

import top.lcm668.study.oj.base.sortmethods.BaseSort;

/**
 * @author: Coder-Lcm
 * @date: 2021/10/5 8:18
 * 归并排序的基类
 */
public abstract class BaseMergeSort<T extends Comparable<T>> extends BaseSort<T>{

    /**
     * 辅助数组，归并排序无法直接在原数组中完成
     */
    protected T[] helperArr;

    /**
     * 归并方法
     * @param arr
     * @param l
     * @param m
     * @param h
     */
    protected void merge(T[] arr, int l, int m, int h) {
        int i = l, j = m + 1;
        for (int i1 = l; i1 <= h; i1++) {
            // 将数据从原数组中复制一份到辅助数组
            helperArr[i1] = arr[i1];
        }

        for (int i2 = l; i2 <= h; i2++) {
            if (i > m) {
                arr[i2] = helperArr[j++];
            } else if (j > h) {
                arr[i2] = helperArr[i++];
            } else if (helperArr[i].compareTo(helperArr[j]) <= 0) {
                arr[i2] = helperArr[i++];
            } else {
                arr[i2] = helperArr[j++];
            }
        }
    }
}
